package DP;

import java.util.Arrays;

/**
 * @Classname 统计字典序元音字符串的数目1614
 * @Description TODO
 * @Date 2023/3/31 7:59
 * @Created by xjl
 */
public class 统计字典序元音字符串的数目1614 {

    /**
     * @description 采用的是的一维数组的压缩存储空间
     * f(i,j)=
     * @param: n
     * @date: 2023/3/31 8:02
     * @return: int
     * @author: xjl
     */
    public int countVowelStrings(int n) {
        int[] dp = new int[5];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < 5; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return Arrays.stream(dp).sum();
    }

    public int countVowelStrings2(int n) {
        int[][] dp = new int[n][5];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < 5; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return Arrays.stream(dp[n]).sum();
    }
}
